import java.util.ArrayList;
import java.util.Arrays;

public class permutation {
    // 全排类
    public String[] _permutation(String s) {
        StringBuilder sb = new StringBuilder();
        char[] chs = s.toCharArray();
        // 排序
        Arrays.sort(chs);
        ArrayList<String> res = new ArrayList<>();
        boolean[] visited = new boolean[chs.length];
        dfs(chs, sb, res, visited);
        String[] ans = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }

    private void dfs(char[] chs, StringBuilder sb, ArrayList<String> res, boolean[] visited) {
        if (sb.length() == chs.length) {
            res.add(sb.toString());
            return;
        }

        for (int start = 0; start < chs.length; start++) {
            if (visited[start] || (start > 1 && !visited[start - 1] && chs[start] == chs[start - 1]))// 去重
                continue;
            visited[start] = true;
            sb.append(chs[start]);
            dfs(chs, sb, res, visited);
            visited[start] = false;
            sb.deleteCharAt(sb.length() - 1);
        }

    }

    public static void main(String[] args) {
        new permutation()._permutation("aab");
    }
}
